package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code85CoinChange {

    public int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }

        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        dp[n][0] = 0;
        // 最后一行 >0 的表示: rest != 0;
        for (int i = 1; i <= amount; i++) {
            dp[n][i] = Integer.MAX_VALUE;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int rest = 0; rest <= amount; rest++) {
                int min = Integer.MAX_VALUE;
                // 选当前硬币
                if (rest >= coins[i]) {
                    int next = dp[i][rest - coins[i]];
                    if (next != Integer.MAX_VALUE) {
                        min = Math.min(min, next + 1);
                    }
                }
                // 不选当前硬币
                dp[i][rest] = Math.min(min, dp[i + 1][rest]);
            }
        }
        return dp[0][amount] == Integer.MAX_VALUE ? -1 : dp[0][amount];
    }

    public int coinChange1(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }

        int min = process(coins, 0, amount);
        return min == Integer.MAX_VALUE ? -1 : min;
    }

    public int process(int[] coins, int index, int rest) {
        if (index == coins.length) {
            // 全部硬币尝试完毕
            return rest == 0 ? 0 : Integer.MAX_VALUE;
        }
        int min = Integer.MAX_VALUE;
        // 选当前硬币
        if (rest >= coins[index]) {
            int next = process(coins, index, rest - coins[index]);
            if (next != Integer.MAX_VALUE) {
                min = Math.min(min, next + 1);
            }
        }
        // 不选当前硬币
        return Math.min(min, process(coins, index + 1, rest));
    }
}
